package 排序;

public class InsertionSort<E extends Comparable<E>> extends Sort<E>{

	

	

	/*@Override
	protected void sort() {
		for (int begin = 1; begin < array.length; begin++) {
			int cur = begin;
			while (cur > 0 && cmp(cur, cur - 1) < 0) {
				swap(cur, cur - 1);
				cur--;
			}
		}
	}*/
	
	/**
	 * 优化一, 减少交换次数
	 */
/*	@Override
	protected void sort() {
		for (int begin = 1; begin < array.length; begin++) {
			E element = array[begin];
			int cur = begin;
			while (cur > 0 && cmp(element, array[cur - 1]) < 0) {
				array[cur] = array[cur - 1];
				cur--;
			}
			array[cur] = element;
		}
	}*/
	
	/**
	 * 优化二, 使用二分查找
	 */
	@Override
	protected void sort() {
		for (int begin = 1; begin < array.length; begin++) {
			E insertElement = array[begin];
			int insertIndex = findInsertIndex(begin);
			for (int i = begin; i > insertIndex; i--) {
				array[i] = array[i - 1];
			}
			array[insertIndex] = insertElement;
		}
	}
	
	
	private int findInsertIndex(int index) {
		E element = array[index];
		int begin = 0;
		int end = index;
		while (begin < end) {
			int mid = (begin + end) >> 1;
			if (cmp(element, array[mid]) < 0) {
				end = mid;
			} else {
				begin = mid + 1;
			}
		}
		return begin;
	}
}
